package com.coder.algorithm.offer_2;

import java.util.Deque;

/**
 * 队列的最大值
 *
 * @author yuhushuan
 * @date 2020/7/2 18:22
 */
public class _59_2_QueueWithMax {
    private class InternalData {
        int number;
        int index;
    }

    private Deque<InternalData> data;
    private Deque<InternalData> max;
    private int currentIndex = 0;

    public void pushLast(Integer number) {
        while (!max.isEmpty() && number >= max.peekLast().number){
            max.pollLast();
        }
        InternalData internalData = new InternalData();
        internalData.number = number;
        internalData.index = currentIndex;

        max.offerLast(internalData);
        data.offerLast(internalData);

        currentIndex++;
    }

    public Integer popFirst() throws Exception {
        if (max.isEmpty()){
            return null;
        }
        if (max.peekFirst().index == data.peekFirst().index){
            max.pollFirst();
        }
        return data.pollFirst().number;
    }

    public Integer max(){
        if (max.isEmpty()){
            return null;
        }
        return max.peekFirst().number;
    }
}
